package T688;

public class Main {
}

class Solution {
    public static void main(String[] args) {
        System.out.println(knightProbability(3, 2, 0, 0));
    }

    public static double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k+1][n][n];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = 0; l < n; l++) {
                    dp[i][j][l] = -1;
                }
            }
        }
        return f2(n, k, row, column, dp);
    }

    public static double f2(int n, int k, int row, int column, double[][][] dp) {
        if (row < 0 || row >= n || column < 0 || column >= n) {
            return 0;
        }
        if(dp[k][row][column]!=-1) {
            return dp[k][row][column];
        }
        double ans = 0;

        if (k == 0) {
            ans =  1;
        }else {
            ans += f2(n, k-1, row - 1, column - 2, dp) / 8;
            ans += f2(n, k-1, row - 2, column - 1, dp) / 8;
            ans += f2(n, k-1, row - 1, column + 2, dp) / 8;
            ans += f2(n, k-1, row + 1, column + 2, dp) / 8;
            ans += f2(n, k-1, row + 2, column + 1, dp) / 8;
            ans += f2(n, k-1, row + 2, column - 1, dp) / 8;
            ans += f2(n, k-1, row + 1, column - 2, dp) / 8;
            ans += f2(n, k-1, row - 2, column + 1, dp) / 8;

        }
        dp[k][row][column] = ans;
        return ans;
    }

    /**
     * @param n      n*n的棋盘
     * @param k      移动k次
     * @param row    row行
     * @param column col列
     * @return
     */
    public static double knightProbability1(int n, int k, int row, int column) {
        return f1(n, k, row, column);
    }

    public static double f1(int n, int k, int row, int column) {
        if (row < 0 || row >= n || column < 0 || column >= n) {
            return 0;
        }
        double ans = 0;

        if (k == 0) {
            ans =  1;
        }else {
            ans += f1(n, k-1, row - 1, column - 2) / 8;
            ans += f1(n, k-1, row - 2, column - 1) / 8;
            ans += f1(n, k-1, row - 2, column + 1) / 8;
            ans += f1(n, k-1, row - 1, column + 2) / 8;
            ans += f1(n, k-1, row + 1, column + 2) / 8;
            ans += f1(n, k-1, row + 2, column + 1) / 8;
            ans += f1(n, k-1, row + 2, column - 1) / 8;
            ans += f1(n, k-1, row + 1, column - 2) / 8;
        }


        return ans;
    }
}